package math.leetcode_169;

public class QuickSelect {
    public int majorityElement(int[] nums) {
        return quickSelect(nums, 0, nums.length - 1, nums.length / 2);
    }

    public int quickSelect(int[] nums, int lo, int hi, int target) {
        if (lo >= hi) {
            return nums[lo];
        }
        int pivotIndex = partition(nums, lo, hi);
        if (pivotIndex == target) {
            return nums[pivotIndex];
        } else if (pivotIndex > target) {
            return quickSelect(nums, lo, pivotIndex - 1, target);
        } else {
            return quickSelect(nums, pivotIndex + 1, hi, target);
        }
    }

    public int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo];
        int left = lo;
        int right = hi;
        while (left < right) {
            while (left < right && nums[right] > pivot) {
                right--;
            }
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        nums[lo] = nums[left];
        nums[left] = pivot;
        return left;
    }
}
